#include <QVector>
#include <QQueue>
#include <QDebug>

// 站点数据类型
struct StopDatatype
{
    QString name;
    QVector<int> routes;
};

// 路线数据类型
struct RouteDatatype
{
    QString name;
    QVector<int> stops;
};

// 宽度优先搜索函数
void breadthFirstSearch(const QVector<StopDatatype> &stops, const QVector<RouteDatatype> &routes, int startStopIndex, int endStopIndex)
{
    // 创建一个队列，用于存储待搜索的站点
    QQueue<int> queue;

    // 创建一个数组，用于记录每个站点是否已访问过
    QVector<bool> visited(stops.size(), false);

    // 创建一个数组，用于记录每个站点在搜索路径中的前一个站点
    QVector<int> previous(stops.size(), -1);

    // 将起始站点加入队列，并标记为已访问
    queue.enqueue(startStopIndex);
    visited[startStopIndex] = true;

    bool found = false; // 标记是否找到目标站点

    // 开始宽度优先搜索
    while (!queue.isEmpty())
    {
        int currentStopIndex = queue.dequeue();

        if (currentStopIndex == endStopIndex)
        {
            found = true;
            break;
        }

        const StopDatatype &currentStop = stops[currentStopIndex];

        // 遍历当前站点所在的全部路线
        for (int routeIndex : currentStop.routes)
        {
            const RouteDatatype &currentRoute = routes[routeIndex];

            // 遍历当前路线上的全部站点
            for (int nextStopIndex : currentRoute.stops)
            {
                if (!visited[nextStopIndex])
                {
                    queue.enqueue(nextStopIndex);
                    visited[nextStopIndex] = true;
                    previous[nextStopIndex] = currentStopIndex;
                }
            }
        }
    }

    // 根据搜索结果输出路径
    if (found)
    {
        QVector<int> path;
        int currentIndex = endStopIndex;

        while (currentIndex != -1)
        {
            path.prepend(currentIndex);
            currentIndex = previous[currentIndex];
        }

        qDebug() << "从" << stops[startStopIndex].name << "到" << stops[endStopIndex].name << "的路线：";

        if (path.size() == 1)
        {
            qDebug() << "直达";
        }
        else
        {
            for (int i = 0; i < path.size() - 1; ++i)
            {
                int currentStopIndex = path[i];
                int nextStopIndex = path[i + 1];

                const StopDatatype &currentStop = stops[currentStopIndex];
                const StopDatatype &nextStop = stops[nextStopIndex];

                // 查找连接两个站点的路线
                QVector<int> commonRoutes;

                for (int routeIndex : currentStop.routes)
                {
                    if (nextStop.routes.contains(routeIndex))
                    {
                        commonRoutes.append(routeIndex);
                    }
                }

                qDebug() << "通过路线：";
                for (int routeIndex : commonRoutes)
                {
                    qDebug() << routes[routeIndex].name;
                }

                qDebug() << "中转站点：" << nextStop.name;
            }
        }
    }
    else
    {
        qDebug() << "暂不支持直达";
    }
}

int main()
{
    // 假设有以下站点和路线数据
    QVector<StopDatatype> stops = {
        {"stop0", {0}},
        {"stop1", {1, 2}},
        {"stop2", {0, 1}},
        {"stop3", {2}}};

    QVector<RouteDatatype> routes = {
        {"route0", {0, 2}},
        {"route1", {2, 1}},
        {"route1", {1, 3}}};

    // 假设要搜索从stopA到stopB的路径
    int startStopIndex = 0;
    int endStopIndex = 3;

    // 执行宽度优先搜索
    breadthFirstSearch(stops, routes, startStopIndex, endStopIndex);

    return 0;
}
